package com.leetcode;

/**
 * 62. 不同路径
 *
 * @author yml
 * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
 * <p>
 * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
 * <p>
 * 问总共有多少条不同的路径？
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/unique-paths
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode62 {


    /**
     * 这是排列组合题，从起点到终点每种情况的步数都是相同的，横着必须走 (n - 1) 步，竖着必须走 (m - 1) 步。
     * 总步数为 t = (m + n - 2) 步，全排列为 t! (t的阶乘)，但会有很多重复，因为横步和竖步是无序的。
     * 所以结果应该为 [t! / (n - 1)! / (m - 1)!]
     *
     * @param m 行数
     * @param n 列数
     */
    public static int uniquePaths(int m, int n) {
        if (m == 1 || n == 1) return 1; // 只有一排或者一列，路径只有一条

        int t = m + n - 2;
        int maxStep = Math.max(m, n) - 1;
        int minStep = Math.min(m, n) - 1;

        long res = 1, j = 2;
        for (int i = maxStep + 1; i <= t; i++) {
            res *= i;
            if (j <= minStep && res % j == 0) {
                res /= j;
                j++;
            }
        }
        return (int) res;
    }

}
